package com.skh.linkedlist;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @Author: skh
 * @Date: 2019/6/13 15:37
 * @Description: 234.回文联表
 */
public class IsPalindrome {

    /*
    请判断一个链表是否为回文链表。

    示例 1:

    输入: 1->2
    输出: false
    示例 2:

    输入: 1->2->2->1
    输出: true
     */

    /*
    思路:将链表数据压入栈中，后面对比一半就行
     */

    public boolean isPalindrome(ListNode head) {
        Stack<Integer> stack = new Stack();

        ListNode cur = head;
        int count = 0;
        while (cur != null) {
            stack.push(cur.val);
            cur = cur.next;
            count++;
        }

        for (int i = 1; i <= count/2; i++) {
            if (stack.pop() != head.val) {
                return false;
            }
            head = head.next;
        }

        return true;
    }


    /*
    其一，find mid node 使用快慢指针找到链表中点。 其二，reverse 逆序后半部分。 其三，check 从头、中点，开始比较是否相同。
     */

    public boolean isPalindrome1(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        //链表中点就是slow,开始逆序
        ListNode pre = null;
        ListNode cur= slow;
        while (cur != null) {
            ListNode tempNode = cur.next;
            cur.next = pre;
            pre = cur;
            cur= tempNode;
        }

        //逆序完成后就是Pre.
        while (pre != null) {
            if (head.val != pre.val) {
                return false;
            }
            head = head.next;
            pre = pre.next;
        }

        return true;
    }

    /**
     * 将链表数据加到list,然后使用双指针判断,数据是否相等
     * @param head
     * @return
     */
    public boolean isPalindrome2(ListNode head) {
        List<Integer> list = new ArrayList<>();
        ListNode cur = head;
        while (cur != null) {
            list.add(cur.val);
            cur = cur.next;
        }

        int prev = 0;
        int last = list.size() - 1;
        while (prev < last) {
            if (!list.get(prev) .equals(list.get(last)) ) {
                return false;
            }
            prev++;
            last--;
        }

        return true;
    }

}
